1. Field of the Invention
This invention relates to computer memory systems and, more particularly, to arrangements in virtual memory systems that maintain consistency in data included in caches in multiprocessing computer systems connected through a common bus interconnect.
2. History of the Prior Art
In order to make the most advantageous use of memory in computer systems and to provide an apparently very large amount of random access memory (RAM) for use by programmers, the use of virtual memory has become prevalent. Virtual memory systems provide more addressable memory than the actual memory which exists in random access memory. Such systems provide a very large number of virtual addresses which, although they appear to be in random access memory, may actually be in any portion of memory in the system including long term memory.
This is accomplished in a demand-paged virtual memory system by dividing random access memory into a number of fixed blocks each of the same size. When a job is placed in memory, its address space is divided into pages of the same size as the blocks, and these pages are stored in the physical pages. Then, although the pages may or may not be physically contiguous, the addresses are maintained as logically contiguous by a memory management system.
This is done by assigning each block of physical memory a virtual address. The memory management unit keeps track of the relationship of the physical and virtual addresses, usually through a series of look-up tables. When information is needed for the operation of a program, its virtual address is converted into its physical memory position by the memory management unit; and the information which is presently necessary to the operation of the process (if not already there) is copied into main memory. Additional information required by the process is called to main memory as it is needed.
Computer systems have long used caches to speed the operation of the system. In a caching system, as information is called from main memory and used, it is also stored along with its address in a small area of especially fast memory called a cache. As each new read or write command is issued, the system looks to the fast cache memory to see if the information exists in the cache. A comparison of the desired address and the addresses in the cache memory is made. If an address in the cache memory matches the address sought, then there is a cache hit (the information is available in the cache). The information in the cache is then accessed so that access to main memory is not required; and the command is processed much more rapidly. If the information is not available in the cache, the new data is retrieved from the main memory and copied into in the cache ready for use. With a well designed caching system, accessed information is found in the cache on an average over ninety percent of the time.
A cache works quite rapidly when it may be directly addressed without the need of going through the memory management unit. A cache used with a virtual memory system can be addressed more efficiently using the virtual address of the information because the virtual address need not be converted to a physical address before the information can be found in the cache. A problem with virtual caches in multiprocessor systems is data consistency or "stale data" associated with address aliases, i.e. two virtual addresses mapping to a common physical address.
Computer systems have been designed which use multiple processors. The use of multiple processors allows various functions or processes to be handled by other than a single central processing unit (CPU) so that the computing power of the overall system is enhanced. When multiple processors are used in a system, it is often advantageous to utilize individual caches with each processor in order to enhance the speed of operation of each individual processor.
One special advantage offered by a multiple processor system is that the processors may share the same data because they may address the same physical memory. However, when multiple virtual caches used by multiple processors do share data, a data consistency problem arises because operations in the caches may not be reflected in the physical memory shared by the two processors at the time any particular processor looks to the physical memory for data. This is an especially difficult problem because the virtual caches involved and, in fact, all of the system memory are considered by the individual processors to be caches distinct to that processor. The virtual caches are addressed by virtual addresses. A virtual address to one processor has no meaning to another processor associated with a different virtual cache even though the two processors utilize caches which hold the same data from the same physical memory. Consequently, multiprocessor computer systems utilizing virtual caches have provided a very difficult consistency problem to the prior art.
The prior art solutions to the data consistency problem created by the use of virtual caches in multiprocessor computer systems have tended to make great use of hardware and, often, to slow the systems.